НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №7
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «Поняття бінарного дерева.
Обхід бінарного дерева. Створення, відображення дерева.
Вставлення, видалення елементів у бінарному дереві»
Варіант № 15
Дата « 19» червня 2022
Мета роботи: набути навичок створення та обробки бінарних дерев.
Теоретичні відомості:
Дерево – це структура даних, що являє собою сукупність елементів і відносин, що утворюють ієрархічну структуру цих елементів.
Кожен елемент дерева називається вершиною (вузлом) дерева. Вершини дерева з’єднані спрямованими дугами, які називають гілками дерева.
Початковий вузол дерева називають коренем дерева, йому відповідає нульовий рівень. Листями дерева називають вершини, в які входить одна гілка і не виходить жодної гілки.
Кожне дерево має такі властивості:
1) існує вузол, в який не входить ні одна дуга (корінь);
2) у кожну вершину, крім кореня, входить одна дуга.
Дерева особливо часто використовують на практиці при зображенні різних ієрархій.
/
Бінарні дерева є деревами зі ступенем не більше двох.
Бінарне (двійкове) дерево − це динамічна структура даних, що являє собою дерево, в якому кожна вершина має не більше двох нащадків.
Таким чином, бінарне дерево складається з елементів, кожен з яких містить інформаційне поле і не більше двох посилань на різні бінарні піддерева. На кожен елемент дерева є рівно одне посилання.
/
Кожна вершина бінарного дерева є структурою, що складається з чотирьох видів полів. Вмістом цих полів будуть відповідно:
інформаційне поле (ключ вершини);
службове поле (їх може бути декілька або жодного);
покажчик на ліве піддерево;
покажчик на праве піддерево;
Процес доступу до елементів дерева називається проходженням дерева.
Існує три способи проходження дерев: послідовний, низхідний та висхідний.
При послідовному методі: спочатку розглядається самий лівий відносно кореня елемент, потім його батьківський вузол, потім правий елемент даної ланки, потім переходять до елемента попереднього рівня, що є батьківським по відношенню до батьківського вузла даної ланки і т. д.Вверх до кореня, а потім від кореня вниз до самого правого елемента.
Операції з деревами При низхідному проходженні дерева порядок обходу елементів зверху-вниз та зліва-направо. Тобто спочатку проходиться корінь, потім його лівий елемент, а потім правий і т.д.
При висхідному проходженні порядок проходження зліва-направо та знизу-вверх. Тобто спочатку проходиться лівий вузол найнижчої ланки, потім правий вузол цієї ланки, а потім їх батьківський вузол і т.д. /
Завдання для виконання:
/
Результат виконання:
/
/
Висновок: під час виконання даної лабораторної роботи було набуто практичних навичок щодо створення та обробки бінарних дерев. Було виконано завдання відповідно варіанту. Програма працює відповідно вимог, усе працює справно.
Посилання на Replit: https://replit.com/join/byayghwlko-tr-15fundamient
Код програми:
#include <iostream>
using namespace std;
class Tree {
int data;
Tree* left;
Tree* right;
public:
Tree();
Tree(int tdata);
void treePrint(Tree* tree, int level);
void treeFilling(int data);
void replaceZeros(Tree* tree);
void sonsSum(Tree* tree, int counter);
};
Tree::Tree(){
left = NULL;
right = NULL;
};
Tree::Tree(int tdata) {
data = tdata;
left = NULL;
right = NULL;
}
void Tree::treePrint(Tree* tree, int level=0)
{
if (tree)
{
treePrint(tree->left, level + 1);
for (int i = 0; i < level; i++) cout << " ";
cout << tree->data << endl;
treePrint(tree->right, level + 1);
}
}
void Tree::treeFilling(int data) {
Tree* temp = this;
while(true) {
if(data < temp->data) {
if (temp->left == NULL)
{
temp->left = new Tree;
temp->left->data = data;
...
